A primary consideration in the field of video data processing applications is the time involved in executing operations on the extremely large quantities of data involved. As modern displays become ever more sophisticated, larger volumes of more complex data are involved. For example, typical low-end displays are becoming available having a dimension of 1000.times.1000 pixels or 1 million pixels values. More particularly in the field of color graphics, each pixel is represented by a significant plurality of bits (often 24 bit) representing red, green and blue intensity values which must be processed in complex video data processing applications. When a single host processor must handle all graphic computations, the result typically is an unacceptably long execution time. It is relatively well known in the computer art that where a given problem requires a great many computations that a certain amount of time can be saved by performing certain computations in parallel. In video data processing this can be done by employing a plurality of processors to simultaneously operate on different parts of the image. One solution is to have a plurality of simple processors with a processor for every pixel in the image. A special purpose control processor issues data and special instructions to each of the plurality of pixel processors. It has similarly been known to arrange such pixel processors variously in an array, or in a line wherein the whole raster scan image can be processed concurrently, a line at a time, or as subsets of the array, i.e., sub arrays.
Although such systems have been known in the prior art, they have not been widely used due to the system overhead of supplying data and commands to the plurality of pixel processors and subsequently storing the data produced in the frame buffers. Also, in such applications the frame buffers themselves become very complex. Accordingly only very simple pixel operations have been performed by such prior art multiprocessor systems as exemplified by the following publications.
i) Fuchs, H. Poulton, I., Paeth, A and Bell A., "Developing Pixel Planes, A Smart Memory Based Roster Graphics System," 1982 conferenced on Advanced Research in VLSI, at MIT, Jan 17, 1982 pp. 137-146. PA1 ii) Clark, J. H., and Hannah, M. R. "Distributed Processing in a High Performance Smart Image Memory", Lambda, 4th Quarter 1980 pp. 40-45.
As indicated above, the types of operations which have heretofore been available with such processor per pixel video architectures have been extremely limited in nature and, more particularly, limited in the complexity of the operations performed. In the field of color graphics, due to the amount of data involved per pixel, the manipulative operations become quite complex and frequently require relatively involved computations as compared to black/white or grayscale operations. The types of applications that have been envisioned for color graphics are complex, and have been limited due to the large amount of time necessary to perform the operations on a pixel by pixel basis. Further, due to the complexity of the operations, it has never been considered feasible to perform such operations as shading of three-dimensional images and anti-aliasing on anything approaching a processor per pixel type of display architecture which might be constructed as an SIMD pixel processor architecture.
In video displays, when projecting a three-dimensional image onto a two-dimensional surface, the attaining of uniformly shaded areas in the polygons making up the image and anti-aliasing of the intersecting edges of these polygons to provide an enhanced image has always been a complex problem. The basic geometry for providing the shading and anti-aliasing has long been known as will be set forth more fully subsequently. However, providing such enhanced images via an SIMD architecture has never been considered feasible due to the complexity of the computations which must be performed. Hence, such image upgrading is conventionally done serially, pixel by pixel in a host or image processor.
In such color images, the triangle is the primitive shape for modeling three-dimensional surfaces. Although rectangles have also been used, triangles have the important advantage that they retain their planarity under perspective transformation. To render a three-dimensional surface, the triangles are projected onto a two-dimensional surface, the image plane. The triangles are drawn from back to front to remove hidden surfaces (by known algorithms). In order to provide optimized displays, it is desired that each triangle be smoothly shaded and have anti-aliased edges. This is well known. The smooth shading creates the effect of a continuous surface, and anti-aliasing of edges results in smooth rather than jagged boundaries which further contribute to the effect of continuity of the displayed image. Conventional serial systems have not been able to generate such images at acceptable speeds. The herein disclosed invention greatly improves this situation by exploiting parallelism in an economical SIMD pixel processing architecture realizing a novel program which is run identically on each processor and contains the requisite data modification constructs whereby each processor is capable of modifying its own particular pixel in an array of pixels to produce a smoothly shaded, anti-aliased, three-dimensional image on the display screen.